package problem.ej1;

public class Ejercicio1
{
	static int contador;
	// Busco primero el minimo desde el principio al final, me guardo ese minimo y el indice
	// Despues busco el maximo(minimo_max) desde ese indice hacia adelante y lo guardo.
	// Recorro de nuevo el arreglo y busco el maximo, me guardo el indice.
	// Desde ese indice hacia atras, voy a buscar el minimo(maximo_min).
	// resto los dos resultados y obtengo dos soluciones, me fijo cual es mayor y la devuelvo
	
	public int precio2(int a, int[] precios) // O(4*n)
	{
		int i;
		int minimo = precios[0];
		int indice_min = 0;
		int indice_max = 0;
		int minimo_max;
		int maximo_min;
		
		// busco el minimo.
		for (i = 0; i < a; i++) //O(a) a = n
		{
			contador ++;
			if (precios[i] < minimo)
			{
				minimo = precios[i];
				indice_min = i;
			}
		}
		
		minimo_max = precios[indice_min];
		// ahora voy a buscar el maximo desde el minimo hacia adelante.
		for (i = indice_min; i < a; i++) // O(a - indice_min) --> O(n) 
		{
			contador++;
			if (precios[i] > minimo_max)
			{
				minimo_max = precios[i];
			}
		}
		
		//Aca ya tengo minimo y minimo_max
		
		int result1 = minimo_max - minimo; 
		
		// busco el maximo.
		int maximo = minimo;
		
		for (i = 0; i < a; i++) // O(a) a = n
		{
			contador++;
			if (precios[i] > maximo)
			{
				maximo = precios[i];
				indice_max = i;
			}
		}
		
		maximo_min = precios[indice_max];
		
		// ahora busco el minimo hacia atras, empezando desde el maximo que encontre.
		for (i = indice_max; i > 0; i--) // O(indice_max) --> O(n)
		{
			contador++;
			if (precios[i] < maximo_min)
			{
				maximo_min = precios[i];
			}
		}
		
		int result2 = maximo - maximo_min;
		
		return max(result1,result2); // O(1)
	}
	
	// Empiezo por el principio y voy barriendo hasta el final, sabiendo que los primeros solo pueden ser solucion si encuentro algun otro elemento mas chico
	// y que est� primero,
	// puedo ir recorriendolo desde adelante y guardandome el minimo e ir comparandolo con los que tienen posibilidades de ser soluciones.
	
	// ESTE ES EL ALGORITMO QUE VAMOS A USAR.
	
	public int precio(int tamano, int[] precios) //O(n)
	{
		int minimo = 999999;
		int posible_minimo = 0;
		int solucion = 0;
		for (int i = 0; i < (tamano - 1); i++)
		{
			contador++;
			if(precios[i] < precios[i+1])
			{
				posible_minimo = precios[i];
				contador++;
				if(posible_minimo < minimo)
				{
					minimo = posible_minimo;
					contador++;
				}
				
				solucion = max(solucion,(precios[i+1] - minimo)); 
				contador++;
			}
		}
		return solucion;
	}
	
	private int max(int result1, int result2)
	{
		if (result1 > result2)
		{
			return result1;
		}
		else
		{
			return result2;
		}
		
	}
}
